# -*- coding: utf-8 -*-

"""
    Time    : 2020/12/22 下午3:33
    Author  : Thinkgamer
    File    : 069-x的平方根.py
    Software: PyCharm
    Desc    : https://leetcode-cn.com/problems/sqrtx/
"""
"""
实现 int sqrt(int x)函数。
计算并返回 x 的平方根，其中 x 是非负整数。
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:
输入: 4
输出: 2

示例 2:
输入: 8
输出: 2

说明: 8 的平方根是 2.82842..., 
    由于返回类型是整数，小数部分将被舍去。
"""


# 二分法
# 32ms 59.05% | 2.9mb 41.96%
def my_sqrt(x):
	if x == 0:
		return 0
	left = 1
	right = x
	while left <= right:
		mid = (left + right) // 2
		sqrt = x // mid
		if sqrt < mid:
			right = mid - 1
		elif sqrt > mid:
			left = mid + 1
		else:
			return mid

	return right


# 牛顿迭代法 x_{n+1} = (x_n + a/x_n) / 2
# 56 ms 12.69% | 12.9mb 40.59%
def my_sqrt_v2(x):
	a = x
	while a * a > x:
		a = int((a + x/a) / 2)

	return int(a)


for x in [1, 2, 4, 8, 16, 2147395599]:
	result = my_sqrt(x)
	print(result)
